package com.simon.study.algorithm.shuntingyard;

import cn.hutool.core.collection.CollectionUtil;
import java.io.Serializable;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import lombok.NoArgsConstructor;

/**
 * <p>
 *
 * @author simon
 * @date 2022/8/22 5:03 下午
 */
public class ShuntingYard {

    public static final int PAL   = 99;   // (
    public static final int PAR   = 100;  // )

    @NoArgsConstructor
    public static class Token implements   Serializable{
        char lexeme;
        int  prior;      // default == 0;

        public Token(char lexeme) {
            this.lexeme = lexeme;
        }
    }

    public static void main(String[] args) {
        String s1 = "1+2*3+4";
        toSuffix(s1);
        // 123*+4+

        s1 = "1 + 2 *  (4 + 5 - 6) ";
        toSuffix(s1);
        // 1245+6-*+

        s1 = "1 + 2 * (3 + (4 + 5 - 6) * 2)";
        toSuffix(s1);
        // 12345+6-2*+*+
        // 1 2 3 4 5 + 6 - 2 * + * +

        s1 = "a + b * c + ( d * e + f ) * g";
        toSuffix(s1);
        // abc*+de*f+g*+
        // a b c * + d e * f  + g * +
    }

    public static List<Token> parse(String expr){
        expr = expr.replaceAll("\\s+", "");
        System.out.println(expr);

        List<Token> tokens = new ArrayList<>();
        for (char ch : expr.toCharArray()) {
            Token token = new Token(ch);
            Integer prior = OP_MAP.get(Character.valueOf(ch));
            if(Objects.nonNull(prior)){ token.prior = prior; }

            tokens.add(token);
        }
        return tokens;
    }

    public static void toSuffix(String expr){
        printTokens(shuntingYard(parse(expr)));
    }


    public static String printTokens(List<Token> tokens){
        if( CollectionUtil.isEmpty(tokens) ) { return ""; }

        StringBuilder sb = new StringBuilder();
        for (Token token : tokens) {
            sb.append(token.lexeme);
        }
        String rst = sb.toString();
        System.out.println(rst);
        return rst;
    }

    public static List<Token> shuntingYard(List<Token> tokens){
        if( CollectionUtil.isEmpty(tokens) ) { return null; }

        Deque<Token> opStack = new ArrayDeque<>();
        List<Token> postExpr = new ArrayList<>();

        for (Token token : tokens) {
            if(!operator(token)){ postExpr.add(token);}

            else if(token.prior == PAL){
                opStack.push(token);
            }
            else if(token.prior == PAR){
                while (!opStack.isEmpty() && opStack.peek().prior != PAL){
                    postExpr.add(opStack.pop());
                }
                opStack.pop();
            }
            else{
                while (!opStack.isEmpty()
                        && opStack.peek().prior >= token.prior
                        && opStack.peek().prior != PAL
                ){
                    postExpr.add(opStack.pop());
                }
                opStack.push(token);
            }
        }

        while (!opStack.isEmpty()){ postExpr.add(opStack.pop()); }

        return postExpr;
    }


    public static final Map<Character, Integer> OP_MAP = new HashMap<>();
    static {
        OP_MAP.put('+', 10);
        OP_MAP.put('-', 10);
        OP_MAP.put('*', 20);
        OP_MAP.put('/', 20);
        OP_MAP.put('(', PAL);
        OP_MAP.put(')', PAR);
    }

    public static boolean operator(Token token){
        return OP_MAP.values().contains(token.prior);
    }
}
